package org.tonny.algorithm.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 735. 行星碰撞
 */
public class LeetCode735 {
    public int[] asteroidCollision(int[] asteroids) {
        if (asteroids == null) {
            return new int[0];
        }
        if (asteroids.length == 0 || asteroids.length == 1) {
            return asteroids;
        }
        Stack<Integer> tmp = new Stack<>();
        for (int i = 0; i < asteroids.length; i++) {
            int asteroid = asteroids[i];
            if (tmp.isEmpty()) {//如果栈为空，直接加入
                tmp.push(asteroid);
                continue;
            }
            int top = tmp.peek();
            if (top < 0) {//顶端小于0，不用考虑后面的元素，直接添加
                tmp.push(asteroid);
                continue;
            }

            //top>0,asteroid > 0,符号相等，直接添加
            if (asteroid > 0) {
                tmp.push(asteroid);
                continue;
            }
            //top>0&&asteroid<0&&top>-asteroid的情况,丢弃asteroid
            if (top > -asteroid) {
                continue;
            }
            ///top>0&&asteroid<0&&top==-asteroid的情况,丢弃top，丢弃asteroid
            if (top == -asteroid) {
                tmp.pop();
                continue;
            }
            //top>0&&asteroid<0&&top<-asteroid。丢弃top,恢复游标，继续处理
            tmp.pop();
            i--;
        }
        int size = tmp.size();
        int[] result = new int[size];
        while (tmp.size() > 0) {
            result[--size] = tmp.pop();
        }
        return result;
    }
}